/*
 * @lc app=leetcode.cn id=337 lang=cpp
 *
 * [337] 打家劫舍 III
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
   public:
    map<TreeNode *, int> f;

    int rob(TreeNode *root) {
        // 递归终止条件，当前节点为 nullptr
        if (root == nullptr) return 0;

        // 第一种情况，打劫当前节点
        int ans1 = root->val;
        if (root->left != nullptr) {
            if (f.count(root->left->left) == 0) {
                f[root->left->left] = rob(root->left->left);
            }
            if (f.count(root->left->right) == 0) {
                f[root->left->right] = rob(root->left->right);
            }
            ans1 += f[root->left->left];
            ans1 += f[root->left->right];
        }
        if (root->right != nullptr) {
            if (f.count(root->right->left) == 0) {
                f[root->right->left] = rob(root->right->left);
            }
            if (f.count(root->right->right) == 0) {
                f[root->right->right] = rob(root->right->right);
            }
            ans1 += f[root->right->left];
            ans1 += f[root->right->right];
        }

        // 第二种情况，不打劫当前节点
        if (f.count(root->left) == 0) {
            f[root->left] = rob(root->left);
        }
        if (f.count(root->right) == 0) {
            f[root->right] = rob(root->right);
        }
        int ans2 = f[root->left] + f[root->right];

        // 返回两种情况中的较大值
        return max(ans1, ans2);
    }
};
// @lc code=end
